package matrix_map

import (
	"container/list"
)

type MMap struct {
	NodeSize  int64
	NodeCount int64
	MatrixArr []int
	NodeArr   []MNode
}

func NewMMap(nodeSize int64) *MMap {
	return &MMap{
		NodeSize:  nodeSize,
		NodeCount: 0,
		MatrixArr: make([]int, nodeSize*nodeSize),
		NodeArr:   make([]MNode, nodeSize),
	}
}

type MNode struct {
	HasVisible bool
	Data       interface{}
}

func NewMNode(data interface{}) *MNode {
	return &MNode{Data: data, HasVisible: false}
}

func (m *MMap) AddNode(node *MNode) bool {
	if m.NodeCount == m.NodeSize {
		return false
	}
	m.NodeArr[m.NodeCount] = MNode{
		HasVisible: false,
		Data:       node.Data,
	}
	m.NodeCount++
	return true
}

func (m *MMap) ResetNode() {
	var i int64;
	for i = 0; i < m.NodeCount; i++ {
		m.NodeArr[i].HasVisible = false
	}
}

func (m *MMap) SetValueToMatrixDirectedGrapth(row int64, col int64, value int) bool {
	if row > m.NodeSize-1 {
		return false
	}
	if col > m.NodeSize-1 {
		return false
	}
	m.MatrixArr[row*m.NodeSize+col] = value
	m.MatrixArr[col*m.NodeSize+row] = value
	return true;
}

func (m *MMap) SetValueToMatrixUnDirectedGrapth(row int64, col int64, value int) bool {
	if row > m.NodeSize-1 {
		return false
	}
	if col > m.NodeSize-1 {
		return false
	}
	m.MatrixArr[row*m.NodeSize+col] = value
	return true
}

func (m *MMap) GetValueFromMatrix(row int64, col int64) (int, bool) {
	if row > m.NodeSize-1 {
		return 0, false
	}
	if col > m.NodeSize-1 {
		return 0, false
	}
	value := m.MatrixArr[row*m.NodeSize+col]
	return value, true;
}

func (m *MMap) PrintMap() {
	var row int64
	var col int64
	print("  ")
	for col = 0; col < m.NodeSize; col++ {
		print(m.NodeArr[col].Data.(string), " ")
	}
	println("")
	for row = 0; row < m.NodeSize; row++ {
		print(m.NodeArr[row].Data.(string), " ")
		for col = 0; col < m.NodeSize; col++ {
			print(m.MatrixArr[row*m.NodeSize+col], " ")
		}
		println("")
	}
}

func (m *MMap)DepthTraverse (nodeIndex int64) {
	m.ResetNode();
	m.depthArrTraverse(nodeIndex)
}

func (m *MMap) depthArrTraverse(nodeIndex int64) {
	print(m.NodeArr[nodeIndex].Data.(string), " ")
	m.NodeArr[nodeIndex].HasVisible = true;
	var col int64
	for col = 0; col < m.NodeSize; col++ {
		value, ok := m.GetValueFromMatrix(nodeIndex, col);
		if ok && value == 1 {
			if m.NodeArr[col].HasVisible == false {
				m.depthArrTraverse(col)
			}
		}
	}
}

func (m *MMap) BreadthTraverse(nodeIndex int64) {
	m.ResetNode();

	m.NodeArr[nodeIndex].HasVisible = true
	print(m.NodeArr[nodeIndex].Data.(string), " ")

	m.breadthArrTraverse([]int64{nodeIndex})
}

func (m *MMap) breadthArrTraverse(vector []int64) {
	var i int64
	var col int64
	var svector []int64
	for i = 0; i < int64(len(vector)); i++ {
		nodeIndex := vector[i]
		for col = 0; col < m.NodeSize; col++ {
			value, ok := m.GetValueFromMatrix(nodeIndex, col)
			if ok && value == 1 {
				if m.NodeArr[col].HasVisible == false {
					m.NodeArr[col].HasVisible = true
					print(m.NodeArr[col].Data.(string), " ")
					svector = append(svector, col)
				}
			}
		}
	}
	if len(svector) > 0 {
		m.breadthArrTraverse(svector)
	}
}

type MEdge struct {
	NodeIndexA int64
	NodeIndexB int64
	HasSelected bool
	WeightValue int64
}

func (m *MMap) KruscalTree() {
	m.ResetNode();
	var edges []MEdge
	var row int64
	var col int64
	var edgeCount int64
	var minEdges []MEdge
	for row = 0; row < m.NodeSize; row++ {
		for col = row + 1; col < m.NodeSize; col++ {
			value, ok := m.GetValueFromMatrix(row, col);
			if ok && value > 0 {
				edges = append(edges, MEdge{
					NodeIndexA:  row,
					NodeIndexB:  col,
					HasSelected: false,
					WeightValue: int64(value),
				})
			}
		}
	}

	if (len(edges) == 0) {
		return
	}

	nodeSets := [][]int64{}

	for edgeCount < m.NodeSize-1 {
		//获取最小边
		minEdgeIndex := m.getMinEdge(edges)
		edges[minEdgeIndex].HasSelected = true

		//最小边顶点
		minEdgeNodeIndexA := edges[minEdgeIndex].NodeIndexA
		minEdgeNodeIndexB := edges[minEdgeIndex].NodeIndexB

		//A顶点所在集合下标
		var nodeSetIndexA int = -1
		for i := 0; i < len(nodeSets); i++ {
			if m.inArray(minEdgeNodeIndexA, nodeSets[i]) {
				nodeSetIndexA = i
				break;
			}
		}
		//B顶点所在集合下标
		var nodeSetIndexB int = -1
		for i := 0; i < len(nodeSets); i++ {
			if m.inArray(minEdgeNodeIndexB, nodeSets[i]) {
				nodeSetIndexB = i
				break;
			}
		}

		if nodeSetIndexA == -1 && nodeSetIndexB == -1 {
			nodeSets = append(nodeSets, []int64{minEdgeNodeIndexA, minEdgeNodeIndexB})
		} else if nodeSetIndexA == -1 && nodeSetIndexB != -1 {
			nodeSets[nodeSetIndexB] = append(nodeSets[nodeSetIndexB], minEdgeNodeIndexA)
		} else if nodeSetIndexA != -1 && nodeSetIndexB == -1 {
			nodeSets[nodeSetIndexA] = append(nodeSets[nodeSetIndexA], minEdgeNodeIndexB)
		} else if nodeSetIndexA != -1 && nodeSetIndexB != -1 && nodeSetIndexA != nodeSetIndexB {
			nodeSets[nodeSetIndexA] = append(nodeSets[nodeSetIndexA], nodeSets[nodeSetIndexB]...)
			nodeSets[nodeSetIndexB] = []int64{};
		} else if nodeSetIndexA != -1 && nodeSetIndexB != -1 && nodeSetIndexA == nodeSetIndexB {
			continue
		}

		minEdges = append(minEdges,edges[minEdgeIndex])
		edgeCount++
		println(minEdgeNodeIndexA, m.NodeArr[minEdgeNodeIndexA].Data.(string), "--->", minEdgeNodeIndexB, m.NodeArr[minEdgeNodeIndexB].Data.(string), ":", edges[minEdgeIndex].WeightValue)
	}
	for i := 0; i < len(nodeSets); i++ {
		if len(nodeSets[i]) > 0 {
			for k:=0; k<len(nodeSets[i]);k++  {
				tempNodeIndex := nodeSets[i][k]
				println(m.NodeArr[tempNodeIndex].Data.(string))
			}
		}
	}
}


func (m *MMap) inArray(val int64,arr []int64) bool{
	for i:=0;i<len(arr);i++{
		if arr[i] == val{
			return true
		}
	}
	return false
}

func (m *MMap) PrimTree(nodeIndex int64){
	m.ResetNode();

	m.NodeArr[nodeIndex].HasVisible = true;
	print(m.NodeArr[nodeIndex].Data.(string), " ")

	nodeStack := list.New()
	nodeStack.PushBack(nodeIndex)

	var i int64
	var edges []MEdge
	var edgeCount int64 = 0;
	var minEdges []MEdge;
	for edgeCount < m.NodeSize-1 {
		tempIndex := nodeStack.Back().Value.(int64)
		for i=0;i<m.NodeSize ;i++  {
			value, ok := m.GetValueFromMatrix(tempIndex, i);if ok && value > 0 {
				if m.NodeArr[i].HasVisible==false{
					edges = append(edges, MEdge{
						NodeIndexA:  tempIndex,
						NodeIndexB:  i,
						HasSelected: false,
						WeightValue: int64(value),
					})
				}
			}
		}

		if edges != nil{
			//获取最小边下标
			minEdgeIndex := m.getMinEdge(edges)

			minEdge := edges[minEdgeIndex]
			edges[minEdgeIndex].HasSelected = true
			minEdges = append(minEdges,edges[minEdgeIndex])
			edgeCount++

			nextNodeIndex := minEdge.NodeIndexB
			nodeStack.PushBack(nextNodeIndex)

			println(minEdge.NodeIndexA,"--->",minEdge.NodeIndexB,":",minEdge.WeightValue)

			m.NodeArr[nextNodeIndex].HasVisible = true;
			print(m.NodeArr[nextNodeIndex].Data.(string), " ")
		}else{
			break;
		}
	}
}

func (m *MMap) getMinEdge(edges []MEdge) int64 {
	var i int64
	var minWeightValue int64
	var minIndex int64 = -1
	for i = 0; i < int64(len(edges)); i++ {
		if edges[i].HasSelected == false {
			minIndex = i
			minWeightValue = edges[i].WeightValue
			break;
		}
	}
	if minIndex < 0 {
		return -1
	}
	var j int64
	for j = minIndex + 1; j < int64(len(edges)); j++ {
		if edges[j].HasSelected == false {
			//println("minWeightValue",edges[j].WeightValue,minWeightValue)
			if (edges[j].WeightValue < minWeightValue) {
				minIndex = j
				minWeightValue = edges[j].WeightValue
			}
		}
	}
	return minIndex
}

